package com.jiajia.study;

import java.util.Comparator;

/**
 * AVL树：平衡二叉搜索树
 * @author : zjj
 * @date : 2021/1/22 10:32
 */
public class AVLTree<E> extends BST<E>{

    public AVLTree(){

    }

    /**
     * 提供给外部的有比较器的构造函数
     * @param comparator    比较器
     */
    public AVLTree(Comparator<E> comparator){
        super(comparator);
    }

    /**
     * 添加节点之后的操作，
     * 平衡二叉树要调整
     * 思路：
     *      找到最先失衡的父节点，然后对该节点进行调整，只要该节点平衡了，整棵树就平衡了
     * @param node 新添加的节点
     */
    @Override
    protected void afterAdd(Node<E> node) {
        while((node = node.parent) != null){
            // 是否平衡
            if(isBalanced(node)){
                // 添加节点之后，去更新父节点的高度
                updateHeight(node);
            }else {
                // 恢复平衡
                reBalanced(node);
                // 整颗树恢复平衡,最先失去平衡的节点恢复了平衡，整棵树就恢复了平衡
                break;
            }
        }
    }

    /**
     * 恢复平衡的第二种方法，统一处理
     * @param grand 最低失去平衡的节点
     */
    private void reBalanced2(Node<E> grand){
        Node<E> parent = ((AVLNode)grand).tallerChild();
        Node<E> node = ((AVLNode)parent).tallerChild();
        if (parent.isLeftChild()) {
            // L
            if (node.isLeftChild()) {
                // LL
               // rotate(grand, node, node.right, parent, parent.right, grand);
            } else { // LR
               // rotate(grand, parent, node.left, node, node.right, grand);
            }
        } else { // R
            if (node.isLeftChild()) {
                // RL
               // rotate(grand, grand, node.left, node, node.right, parent);
            } else { // RR
               // rotate(grand, grand, parent.left, parent, node.left, node);
            }
        }
    }

    /**
     * 恢复平衡
     *
     * @param r 子树的根节点
     * @param a a节点
     * @param b b节点
     * @param c c节点
     * @param d d节点  平衡后的根节点
     * @param e e节点
     * @param f f节点
     * @param g g节点
     */
    private void rotate(
            Node<E> r,
            Node<E> a , Node<E> b , Node<E> c ,
            Node<E> d ,
            Node<E> e , Node<E> f ,Node<E> g
    ){
        // 将d改成子树的根节点
        if(r.isLeftChild()){
            r.parent.left = d ;
        }else if(r.isRightChild()){
            r.parent.right = d;
        }else{
            root = d;
        }

        // 处理 a - b - c的关系
        b.left = a ;
        if(a != null ){
            a.parent = b;
        }
        b.right = c;
        if(c != null ){
            c.parent = b;
        }
        // 处理高度
        updateHeight(b);

        // 处理 e - f - g
        f.left = e ;
        if(e!= null ){
            e.parent = f;
        }
        f.right = g;
        if(g != null){
            g.parent = f;
        }
        // 处理高度
        updateHeight(f);

        // 处理 b - d  - f
        d.left = b ;
        d.right = f;
        b.parent = d ;
        f.parent = d;

    }

    /**
     * 恢复平衡
     * @param grand  高度最低的不平衡的节点，也就是离添加节点最近的那个不平衡节点
     */
    private void reBalanced(Node<E> grand){
        Node<E> parent = ((AVLNode)grand).tallerChild();
        Node<E> node = ((AVLNode)parent).tallerChild();
        if(parent.isLeaf()){
            if(node.isLeftChild()){
                // LL
                rotateRight(grand);
            }else {
                // LR
                rotateLeft(parent);
                rotateRight(grand);
            }
        }else {
            if(parent.isLeftChild()){
                // RL
                rotateRight(parent);
                rotateLeft(grand);
            }{
                // RR
                rotateLeft(grand);
            }
        }

    }

    /**
     * 向左旋转
     * @param grand  节点
     */
    private void rotateLeft(Node<E> grand){
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = parent.left ;
        parent.left = grand;

        afterRotate(grand,parent,child);

    }

    /**
     * 向右旋转
     * @param grand  节点
     */
    private void rotateRight(Node<E> grand){
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;

        afterRotate(grand,parent,child);

    }

    /**
     * 旋转之后一些节点的调整工作：
     * 修改父节点
     * 修改高度
     * @param grand     grand节点
     * @param parent    parent接地那
     * @param child     child节点
     */
    private void afterRotate(Node<E> grand ,Node<E> parent ,Node<E> child){
        // 将parent修改成子树的根节点
        parent.parent = grand.parent;
        if(grand.isLeftChild()){
            grand.parent.left = parent;
        }else if(grand.isRightChild()){
            grand.parent.right = parent;
        }else {
            // 整棵树的根节点
            root = parent;
        }

        // 更新child的父节点
        if(child != null ){

            child.parent = grand ;
        }

        // 更新 grand的父节点
        grand.parent = parent;

        // 更新的高度
        updateHeight(grand);
        updateHeight(parent);
    }
    /**
     * 更新节点的高度
     * @param node  节点
     */
    private void updateHeight(Node<E> node){
        ((AVLNode)node).updateHeight();
    }

    /**
     * 创建AVL类型的节点
     * @param element   节点数据
     * @param parent    父节点
     * @return          AVL节点
     */
    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode(element, parent);
    }

    /**
     * 是否平衡 ，平衡因子的绝对值是否小于等于1
     * @param node  节点
     * @return      是否平衡
     */
    private boolean isBalanced(Node<E> node){
        return Math.abs(((AVLNode)node).balanceFactory()) <= 1;
    }


    /**
     * AVL树节点
     *      继承父类里面的node节点
     * @param <E>   泛型
     */
    private static class  AVLNode<E> extends Node<E>{
        /**
         * 每个节点的高度
         */
        int height;

        public AVLNode(E element, Node<E> parent) {
            super(element, parent);
        }

        /**
         * 平衡因子 ：
         *      左子树的高度 - 右子树的高度
         * @return  平衡因子
         */
        public int balanceFactory(){
            int leftHeight = left == null ? 0 : ((AVLNode)left).height;
            int rightHeight = right == null ? 0 : ((AVLNode)right).height;

            return leftHeight - rightHeight;
        }

        /**
         * 更新当前节点的高度：
         * 左右节点最大高度 + 1
         */
        public void updateHeight(){
            int leftHeight = left == null ? 0 : ((AVLNode)left).height;
            int rightHeight = right == null ? 0 : ((AVLNode)right).height;

            height =  1 + Math.max(leftHeight,rightHeight);
        }

        /**
         * 返回子节点中高度最高的节点
         * @return  高度最高的节点
         */
        public Node<E> tallerChild(){
            int leftHeight = left == null ? 0 : ((AVLNode)left).height;
            int rightHeight = right == null ? 0 : ((AVLNode)right).height;
            if(leftHeight > rightHeight) {
                return left;
            }
            if(leftHeight < rightHeight){
                return right;
            }
            // 左右节点的高度相同，那么如果是父节点的左节点就返回左节点，是父节点的右节点就返回右节点
            return isLeftChild() ? left : right;

        }


    }
}
